package com.leetcode;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No64
 * @description
 * @date 2021/1/27 下午2:48
 */
public class No64 {
    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        int res = minPathSum(grid);
        System.out.println(res);
    }

    public static int minPathSum(int[][] grid) {
        if(grid == null || grid.length < 1 || grid[0].length < 1){
            return 0;
        }
        int rows = grid.length,cols = grid[0].length;
        int[] dp = new int[cols];
        dp[0] = grid[0][0];
        for (int i = 1 ; i < cols; i++) {
            dp[i] = dp[i - 1] + grid[0][i];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if(j == 0){
                    dp[j] += grid[i][j];
                }else{
                    dp[j] = Math.min(dp[j] ,dp[j - 1]) + grid[i][j];
                }
            }
        }
        return dp[cols - 1];
    }

}
